package find;

/**
 * 找一个数组中2个出现奇数次的数
 *
 * @author Liaorun
 */
public class FindTwoOld {
    public static void main(String[] args) {
        int[] ints = {6, 6, 7, 3, 5, 4, 3, 4};

        printOddTimesNum2(ints);
    }

    private static void printOddTimesNum2(int[] arr) {
        int eor = 0;
        for (int i = 0; i < arr.length; i++) {
            eor ^= arr[i];
        }
        // 在arr 中只有两个数字出现奇数次
        // eor = a ^ b and a ！= b   => eor != 0
        // 则这些数字异或的结果 必然至少有一个位置上是1
        // 提取最右的1
        // 一个数和自己的补码 相与 同一为1 否则都为0
        int rightOne = eor & (~eor + 1);

        int onlyOne = 0;
        for (int cur : arr) {
            // 在rightOne 为1的哪一位， cur必须是0，结果才为0
            // (cur & rightOne) == rightOne 也可以
            if ((cur & rightOne) != 0) {
                onlyOne ^= cur;
            }
        }

        System.out.println(onlyOne + " " + (eor ^ onlyOne));
    }
}
